//Cracking coding interview 17_12
//find all pairs of integers with specified sum
//9:42AM--9:55AM--10:30AM(bug free)

#include<vector>
#include<cstdlib>
using namespace std;

struct MyPair {
	MyPair(int iv1, int iv2) {
		v1=iv1;
		v2=iv2;
	}
	int v1, v2;
};

void FindP(int* input, int n, vector<MyPair>& output, int sum) {
	int *headp=input;
	int *endp=input+n-1;
	while(headp!=endp) {
		if(*headp+*endp==sum) {
			if(headp==input || *(headp-1)!=*headp) {
				MyPair a(*headp, *endp);
				output.push_back(a);
			}
			headp++;
			if(headp==endp) break;
			endp--;
		} else if (*headp+*endp<sum) {
			headp++;
		} else {
			endp--;
		}
	}
}

int Cmpair(const void *p1, const void *p2) {
	return *((int*)p1)-*((int*)p2);
}

void FindPair(int* input, int n, vector<MyPair>& output, int sum) {
	if (n<2 || !input) return;
	qsort(input, n, sizeof(int), Cmpair);
	FindP(input, n, output, sum);
}

int main(int argc, char *argv[]) {
	int a[]={1, 4, 9, 3, 72, 7, 6, 4, 6};
	int sum=10;
	vector<MyPair> output;
	FindPair(a, 7, output, 10);

	return 0;
}